package 剑指offer_leetcode;

/**
 * JZ43整数中1出现的次数_从1到n整数中1出现的次数
 */
public class 剑指Offer43_1_n整数中1出现的次数 {
    // 5 0 1 2 2 2  bit
    //cur = (n / bit) % 10   high = (n / bit) / 10    low = n % bit
    // 5 0 1 [2] 2 2  --> 0-501 * 0-99  ==> (high + 1) * bit
    // 5 0 [1] 2 2 2  --> 0-49 * 0-999 + 50   0-222 ==> high * bit + 1 * (low + 1)
    // 5 [0] 1 2 3 3 --> 0-4 * 0-9999  ==> high * bit
    public int countDigitOne(int n) {
        long bit = 1;
        long sum = 0;
        while(bit<=n){
            long cur = (n/bit)%10;
            long high = (n / bit) / 10;
            long low = n % bit;
            if(cur>1)
                sum += (high+1) * bit;
            else if(cur == 1)
                sum += (high * bit) + 1 *(low + 1);
            else
                sum += high * bit;
            bit *=10;
        }
        return (int) sum;

    }
}
